package cn.itcast.algorithm.search;

/**
 * 区间查找
 * create by zhangtian3 on 2019/5/15
 */
public class IntevalSearch {
    /**
     * 区间查找  返回区间最左侧数据
     * 区间[1,1]、[2,2]、[3,3]、[4,4]、[5,5]、[6,10]、[11,20]......
     * 取区间左侧元素二分查找 取左侧元素
     * 1、2、3、4、5、6、11
     * @param nums
     * @param target
     * @return
     */
    public static int intevalSearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1 ;
        }

        int low = 0 ;
        int high = nums.length - 1 ;
        while(low <= high){
            // int mid = (low + high) / 2 ;
            int mid = high - (high - low) /2 ; // 避免二分找找引起的数值越界问题

            if(nums[mid] == target){
                return target ;
            }else if(nums[mid] < target){
                if (mid + 1 <= high) {
                    if (target < nums[mid + 1]) {
                        return nums[mid] ;
                    }else {
                        low = mid + 1 ;
                    }
                }else {
                    return nums[mid] ;
                }

            }else {
                high = mid - 1 ;
            }
        }

        return -1 ;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 11, 21, 31, 51, 101, 501, 1001, 3001, 5001, 7001, 10001} ;
        System.out.println(intevalSearch(nums, 10001));
    }
}
